/**
 * 对二进制数x, 令f(x) = cout_of_1(x)
 * 称作对x的一次约简
 * 
 * 如果在K次操作内能将x约到1，称x为K-可约数
 * 给定s，求比s小的所有正的K可约数
 * 
 * 注意到s长度在800，最多800个1，因此可以预处理
 * 令 U[i] 表示i个1的约简次数
 * 则 U[i] = U[i的1的数量] + 1
 * 
 * 然后做数位DP, 设D[i][j]
 * 其中j表示到目前为止1的数量
 * 在最后返回 U[cnt] <= K 即可
 */
using llt = long long;
llt const MOD = 1E9 + 7;

llt U[801];
llt dp(int status){
    if(-1 != U[status]) return U[status];

    int k = 0;
    int o = status;
    while(status){
        k += status % 2;
        status >>= 1;
    }
    return U[o] = dp(k) + 1;
}

int Limit;
vector<int> G;
// Dij,j表示到目前1的数量
llt D[810][801];
llt dfs(int pos, int cnt, bool lead, bool limit){
    if(-1 == pos) {
        return not lead and dp(cnt) <= Limit ? 1 : 0;
    }
    if(not lead and not limit and -1 != D[pos][cnt]) {
        return D[pos][cnt];
    }
    int last = limit ? G[pos] : 1;
    llt ans = 0;
    for(int i=0;i<=last;++i){
        ans += dfs(pos-1, 1==i?cnt+1:cnt, lead&&0==i, limit&&last==i);
        ans %= MOD;
    }
    if(not lead and not limit){
        D[pos][cnt] = ans;
    }    
    return ans;
}

llt digitDP(const string & s){
    G.clear();
    for(int i=s.length()-1;i>=0;--i){
        G.emplace_back(s[i] - '0');
    }
    return dfs(G.size()-1, 0, true, true);
}

class Solution {
public:
    int countKReducibleNumbers(string s, int k) {
        if(s == "1") return 0;

        Limit = k;
        memset(U, -1, sizeof(U));
        memset(D, -1, sizeof(D));
        U[0] = 0; // 0表示数值1
        U[1] = 1; // 1表示除

        // 将s减一
        k = s.length() - 1;
        while(s[k] == '0') k -= 1;
        s[k] -= 1;
        for(int i=k+1;i<s.length();++i) s[i] = '1';
        return digitDP(s);        
    }
};